🟨扒手I

本題取自 Leetcode 198. House Robber

題目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.


Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.


Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 400

分析

題目可重述如下：

給定一個數列，從中取出若干數，相鄰兩數不能同時取出，求取出的數最大的總和。

例如，我們不能同時取nums[0]和nums[1]

同時取nums[0]、nums[2]或者nums[0]、nums[3]則是可行的。

至於nums[0]、nums[4]雖然也可行，但是一定不會是最佳解，因為所有的數均為正整數，而中間漏掉一個可以取的nums[2]，所以一定比nums[0]、nums[2]、nums[4]來得少。

分治法

延續前幾題費氏數列題型的特徵，可以把子問題定義為：「從index=0~i，所能取出的最大總數為何」

雖然題目規定不可相鄰，但此時界定的問題範圍是0~i，因此只需考慮index=i的「左邊」是否相鄰即可。

至於右邊是否相鄰，只需要留給更大的子問題去思考就好。因為當我們思考更大的子問題，例如index=i+1時，index=i也在他的「左邊」

• 當i=0時，最多可取 nums[0]

• 當i=1時，最多可取 max(nums[0], nums[1])，因為相鄰的兩數只能取一。

• 當i>=2：則有兩種情況：取或者不取nums[i]

  • 如果取了nums[i]，那麼必定不能取相鄰的nums[i-1]，此時

    能取出的最大值 = nums[i] + i-2為止的最大值

  • 如果不取nums[i]，那麼就能取相鄰的nums[i-1]，此時

    能取出的最大值 = i-1為止的最大值

  • 兩者再求其中較大的。

設計狀態、找出轉移式與最小問題

定義狀態money(i)：

nums[0:i+1]當中取出任意數，其中相鄰不可同取，求取出的數最大的總和

注意：這是無論nums[i]是否被取出，均一併考慮之後才求的最大值

轉移式：

money(i) = max( money(i-1) , money(i-2) + nums[i] )

關鍵在於，先確認要不要取nums[i]。

假如不取，就放心參照money(i-1)；假如要取，就參照絕對不會導致相鄰的money(i-2)。

兩種情況都分別考慮之後，再取最大值。

最小狀態

money(0)=nums[0]

money(1)=max(nums[0], nums[1])

實作

Top-Down DP

手刻cache的寫法：

class Solution:
    def rob(self, nums: List[int]) -> int:

        dp = {0:nums[0], 1:max(nums[:2])}
        def money(i):
            if i not in dp: 
                dp[i] = max(nums[i]+money(i-2), money(i-1))
            return dp[i]
        return money(len(nums)-1)

懶人寫法：

class Solution:
    def rob(self, nums: List[int]) -> int:
        @cache
        def money(i):
            if i==0: return nums[0]
            if i==1: return max(nums[:2])
            return max(nums[i]+money(i-2), money(i-1))
        return money(len(nums)-1)

Bottom-Up DP

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [nums[0], max(nums[:2])]

        for i in range(2, len(nums)):
            dp.append(max(nums[i] + dp[i-2], dp[i-1]))

        return dp[-1]

滾動式Bottom-Up DP寫法

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev, curr = (nums[0], max(nums[:2]))

        for i in range(2, len(nums)):
            prev, curr = (curr, max(nums[i] + prev, curr))

        return curr

複雜度分析

本題為1-D DP，狀態數 = O(n)。

時間複雜度

狀態轉移式裡面只做了加法和兩數取大，因此計算複雜度=O(1)。

時間複雜度 = 狀態數 x 計算複雜度 = O(n) x O(1) = O(n)

空間複雜度

需記錄每個狀態的答案，因此空間複雜度為O(n)

若採用rolling Bottom-Up DP，少一維度，空間複雜度為O(1)

🟨扒手II

本題取自 Leetcode 213. House Robber II

題目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.


Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.


Example 3:

Input: nums = [1,2,3]
Output: 3
 

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

分析

和第一題相同，只是測資的nums代表的是一個首尾相鄰的環狀數列。因此，除了陣列的任意相鄰兩數不能同時取之外，還加上了頭尾兩數也不能同時取的限制。

分治法

本題能不能沿用前一題(Leetcode 198. House Robber)的算法呢？實際上是可以的：

既然陣列的頭和尾不能同時取，那麼我們就分別假設它們從一開始便不存在，各自做一次動態規劃就好了！

舉例來說，一個測資有五項：[2,3,5,7,11]，我們就分別對[2,3,5,7]和[3,5,7,11]進行一次動態規劃，再取較大的答案即可。

設計狀態、找出轉移式與最小問題

和前一題相同，我們只需要將給定的陣列掐頭、去尾，各做一次動態規劃再取較大的答案。

實作

程式碼和前一題大同小異，只需要注意一下範圍邊界的調整。假設陣列的長度為n：

第一次計算：計算範圍是0~(n-2) (最後一項不計算)

第二次計算：計算範圍是1~(n-1) (最前面一項不計算)

Top-Down DP

本題直接採用@cache，手刻快取的做法可參考前一題！

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 如果只有一間房子：因為第一間=最後一間，沒有相鄰的問題，可以搶
        if len(nums)<=1: return nums[0]
        
        # 確定不搶最後一間房子的情況
        @cache
        def money1(i):
            if i==0: return nums[0]  # 從第0間
            if i==1: return max(nums[:2])
            return max(nums[i]+money1(i-2), money1(i-1))
        ans1 = money1(len(nums)-2)   # 計算到第n-2間
        
        # 確定不搶第一間房子的情況
        @cache
        def money2(i):
            if i==1: return nums[1]  # 從第1間
            if i==2: return max(nums[1:3])
            return max(nums[i]+money2(i-2), money2(i-1))
        ans2 = money2(len(nums)-1)   # 計算到第n-1間 

        return max(ans1, ans2)       # 最後再求兩種情況較大者

Bottom-Up DP

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 如果只有一間房子：因為第一間=最後一間，沒有相鄰的問題，可以搶
        if len(nums)==1: return nums[0]

        # 確定不搶最後一間房子的情況
        # 從第0間計算到n-2間
        dp = [nums[0], max(nums[:2])]
        for i in range(2, len(nums)-1): 
            dp.append(max(nums[i] + dp[i-2], dp[i-1]))
        ans1 = dp[-1]

        # 確定不搶第一間房子的情況
        # 從第1間計算到n-1間
        # 因為Bottom-Up需要自己建立記錄用的陣列，為了不讓index顯得混亂
        # 直接設第0項為0(小偷不搶第0間 == 第0間搶了0元)
        dp = [0]+[nums[1], max(nums[1:3])]
        for i in range(3, len(nums)):
            dp.append(max(nums[i] + dp[i-2], dp[i-1]))
        ans2 = dp[-1]

        # 最後再求兩種情況較大者
        return max(ans1, ans2)

複雜度分析

和前一題相同，雖然我們整個演算法都需要多執行一次，但因為O(2) = O(1)，並沒有增加複雜度。

結語

在今天的這兩題扒手問題中，我們是這樣定義子問題(狀態)：

目前的這間房子可以搶，也可以不搶，那麼(從第一間到目前為止)最多可以搶多少錢？

並且從中得到這個形式的轉移式：

money(i) = max( money(i-1) , money(i-2) + nums[i] )

事實上，這個問題可以套用一個截然不同的思路：

如果搶匪搶了目前的這間房子，那麼(從第一間到目前為止)最多可以搶多少錢？

作為本日的延伸練習，各位讀者可以想想看，這個思路的轉移式會長什麼樣子呢？

提示：如果確定「搶了」目前的這間房子，那麼前一間被搶的，可能會是那些房子？

在明天的文章中，會給出答案與解釋！

以上為Day4的內容！感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！

本文也同步登載在我的個人部落格，記錄我的學習筆記與生活點滴，歡迎來逛逛。

明天會繼續費波那契數列題型的最後一篇。